{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Frog Position After T Seconds"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: frogPosition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #T 秒后青蛙的位置"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵由 <code>n</code> 个顶点组成的无向树，顶点编号从 <code>1</code> 到 <code>n</code>。青蛙从 <strong>顶点 1</strong> 开始起跳。规则如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>在一秒内，青蛙从它所在的当前顶点跳到另一个 <strong>未访问</strong> 过的顶点（如果它们直接相连）。</li>\n",
    "\t<li>青蛙无法跳回已经访问过的顶点。</li>\n",
    "\t<li>如果青蛙可以跳到多个不同顶点，那么它跳到其中任意一个顶点上的机率都相同。</li>\n",
    "\t<li>如果青蛙不能跳到任何未访问过的顶点上，那么它每次跳跃都会停留在原地。</li>\n",
    "</ul>\n",
    "\n",
    "<p>无向树的边用数组 <code>edges</code> 描述，其中 <code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> 意味着存在一条直接连通 <code>a<sub>i</sub></code> 和 <code>b<sub>i</sub></code> 两个顶点的边。</p>\n",
    "\n",
    "<p>返回青蛙在 <em><code>t</code></em> 秒后位于目标顶点 <em><code>target</code> </em>上的概率。与实际答案相差不超过 <code>10<sup>-5</sup></code> 的结果将被视为正确答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/12/21/frog1.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4\n",
    "<strong>输出：</strong>0.16666666666666666 \n",
    "<strong>解释：</strong>上图显示了青蛙的跳跃路径。青蛙从顶点 1 起跳，第 <strong>1 秒</strong> 有 1/3 的概率跳到顶点 2 ，然后第 <strong>2 秒</strong> 有 1/2 的概率跳到顶点 4，因此青蛙在 2 秒后位于顶点 4 的概率是 1/3 * 1/2 = 1/6 = 0.16666666666666666 。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/12/21/frog2.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7\n",
    "<strong>输出：</strong>0.3333333333333333\n",
    "<strong>解释：</strong>上图显示了青蛙的跳跃路径。青蛙从顶点 1 起跳，有 1/3 = 0.3333333333333333 的概率能够 <strong>1 秒</strong> 后跳到顶点 7 。 \n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>edges.length == n - 1</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= a<sub>i</sub>, b<sub>i</sub>&nbsp;&lt;= n</code></li>\n",
    "\t<li><code>1 &lt;= t &lt;= 50</code></li>\n",
    "\t<li><code>1 &lt;= target &lt;= n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [frog-position-after-t-seconds](https://leetcode.cn/problems/frog-position-after-t-seconds/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [frog-position-after-t-seconds](https://leetcode.cn/problems/frog-position-after-t-seconds/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['7\\n[[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]]\\n2\\n4', '7\\n[[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]]\\n1\\n7']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        adj = defaultdict(list)\n",
    "        for a, b in edges :\n",
    "            adj[a].append(b)\n",
    "            adj[b].append(a)\n",
    "        adj[1].append(0)\n",
    "        # visited = [False for _ in range(n + 1)]\n",
    "        # visited[0] = True\n",
    "        # st = [(1, 1.0, t)]\n",
    "        # dq = deque([(1, 1, t)])\n",
    "        # while dq :\n",
    "        #     root, p, time = dq.popleft()\n",
    "        #     visited[root] = True\n",
    "        #     # m = sum(1 for child in adj[root] if not visited[child])\n",
    "        #     m = len(adj[root]) - 1\n",
    "        #     if root == target :\n",
    "        #         if m == 0 or time == 0:\n",
    "        #             # return p\n",
    "        #             return 1 / p\n",
    "        #         return 0.0\n",
    "        #     if time and m :\n",
    "        #         # p /= m\n",
    "        #         p *= m\n",
    "        #         for child in adj[root] :\n",
    "        #             if not visited[child] :\n",
    "        #                 dq.append((child, p, time - 1))\n",
    "        # return 0.0\n",
    "\n",
    "        q = [(1, 0, 1)]\n",
    "        while q and t >= 0 :\n",
    "            tmp = []\n",
    "            for root, parent, times in q :\n",
    "                m = len(adj[root]) - 1\n",
    "                if root == target :\n",
    "                    if not t or not m :\n",
    "                        return 1 / times\n",
    "                    return 0.0\n",
    "                times *= m\n",
    "                for child in adj[root] :\n",
    "                    if child != parent :\n",
    "                        tmp.append((child, root, times))\n",
    "            q = tmp\n",
    "            t -= 1\n",
    "        return 0.0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef frogPosition(self, n, edges, t, target):\n",
    "\t\tif 1 == target and n == 1:\n",
    "\t\t\treturn 1\n",
    "\t\tg = [[] for _ in range(n + 1)]\n",
    "\t\tfor x, y in edges:\n",
    "\t\t\tg[x].append(y)\n",
    "\t\t\tg[y].append(x)\n",
    "\t\tpending = [(1, 1)]\n",
    "\t\tvisited = [1]\n",
    "\t\tstep = 0\n",
    "\t\twhile pending:\n",
    "\t\t\ttemp = []\n",
    "\t\t\tstep += 1\n",
    "\t\t\tfor v, p in pending:\n",
    "\t\t\t\tif v == 1:\n",
    "\t\t\t\t\tp = 1 / len(g[1])\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tif len(g[v]) - 1:\n",
    "\t\t\t\t\t\tp *= 1 / (len(g[v]) - 1)\n",
    "\t\t\t\tfor node in g[v]:\n",
    "\t\t\t\t\tif node not in visited:\n",
    "\t\t\t\t\t\tif node == target and not len(g[node]) - 1 or node == target and t == step:\n",
    "\t\t\t\t\t\t\treturn p\n",
    "\t\t\t\t\t\ttemp.append((node, p))\n",
    "\t\t\t\t\t\tvisited.append(node)\n",
    "\t\t\tif step == t:\n",
    "\t\t\t\treturn 0\n",
    "\t\t\tpending = temp\n",
    "\t\treturn 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef frogPosition(self, n, edges, t, target):\n",
    "\t\tif 1 == target and n == 1:\n",
    "\t\t\treturn 1\n",
    "\t\tg = [[] for _ in range(n + 1)]\n",
    "\t\tfor x, y in edges:\n",
    "\t\t\tg[x].append(y)\n",
    "\t\t\tg[y].append(x)\n",
    "\t\tpending = [(1, 1)]\n",
    "\t\tvisited = [1]\n",
    "\t\tstep = 0\n",
    "\t\twhile pending:\n",
    "\t\t\ttemp = []\n",
    "\t\t\tstep += 1\n",
    "\t\t\tfor v, p in pending:\n",
    "\t\t\t\t#第一层去往下一层的概率\n",
    "\t\t\t\tif v == 1:\n",
    "\t\t\t\t\tp = 1 / len(g[1])\n",
    "\t\t\t\t#其余层去往下一层的概率\n",
    "\t\t\t\telif len(g[v]) - 1:\n",
    "\t\t\t\t\t#有子节点\n",
    "\t\t\t\t\tp *= 1 / (len(g[v]) - 1)\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tcontinue\n",
    "\t\t\t\t#概率赋给子节点\n",
    "\t\t\t\tfor node in g[v]:\n",
    "\t\t\t\t\tif node not in visited:\n",
    "\t\t\t\t\t\tif node == target and not len(g[node]) - 1 or node == target and t == step:\n",
    "\t\t\t\t\t\t\treturn p\n",
    "\t\t\t\t\t\ttemp.append((node, p))\n",
    "\t\t\t\t\t\tvisited.append(node)\n",
    "\t\t\tif step == t:\n",
    "\t\t\t\treturn 0\n",
    "\t\t\tpending = temp\n",
    "\t\treturn 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        adj = defaultdict(list)\n",
    "        for a, b in edges :\n",
    "            adj[a].append(b)\n",
    "            adj[b].append(a)\n",
    "        visited = [False for _ in range(n + 1)]\n",
    "        # st = [(1, 1.0, t)]\n",
    "        st = [(1, 1, t)]\n",
    "        while st :\n",
    "            root, p, time = st.pop()\n",
    "            visited[root] = True\n",
    "            m = sum(1 for child in adj[root] if not visited[child])\n",
    "            if root == target :\n",
    "                if m == 0 or time == 0:\n",
    "                    # return p\n",
    "                    return 1 / p\n",
    "                return 0.0\n",
    "            if time and m :\n",
    "                # p /= m\n",
    "                p *= m\n",
    "                for child in adj[root] :\n",
    "                    if not visited[child] :\n",
    "                        st.append((child, p, time - 1))\n",
    "        return 0.0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        used = [0] * (n + 1)\n",
    "        d = [[] for _ in range(n + 1)]\n",
    "        for edge in edges:\n",
    "            d[edge[0]].append(edge[1])\n",
    "            d[edge[1]].append(edge[0])\n",
    "\n",
    "        queue = [(1, 1, 0)]\n",
    "        while queue:\n",
    "            cur, prob, time = queue.pop(0)\n",
    "            if used[cur]:\n",
    "                continue\n",
    "            if time > t:\n",
    "                return 0\n",
    "            if cur == target and time == t:\n",
    "                return prob\n",
    "\n",
    "            used[cur] = 1\n",
    "            cnt = len(d[cur])\n",
    "            for n in d[cur]:\n",
    "                if used[n]:\n",
    "                    cnt -= 1\n",
    "            if cnt:\n",
    "                if cur == target and time < t:\n",
    "                    return 0\n",
    "                prob *= (1 / cnt)\n",
    "                time += 1\n",
    "            else:\n",
    "                if cur == target:\n",
    "                    return prob\n",
    "                else:\n",
    "                    continue\n",
    "\n",
    "            for n in d[cur]:\n",
    "                if not used[n]:\n",
    "                    queue.append((n, prob, time))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef frogPosition(self, n, edges, t, target):\n",
    "\t\tif 1 == target and n == 1:\n",
    "\t\t\treturn 1\n",
    "\t\tg = [[] for _ in range(n + 1)]\n",
    "\t\tfor x, y in edges:\n",
    "\t\t\tg[x].append(y)\n",
    "\t\t\tg[y].append(x)\n",
    "\t\tpending = [(1, 1)]\n",
    "\t\tvisited = [1]\n",
    "\t\tstep = 0\n",
    "\t\twhile pending:\n",
    "\t\t\ttemp = []\n",
    "\t\t\tstep += 1\n",
    "\t\t\tfor v, p in pending:\n",
    "\t\t\t\t#第一层去往下一层的概率\n",
    "\t\t\t\tif v == 1:\n",
    "\t\t\t\t\tp = 1 / len(g[1])\n",
    "\t\t\t\t#其余层去往下一层的概率\n",
    "\t\t\t\telif len(g[v]) - 1:\n",
    "\t\t\t\t\t#有子节点\n",
    "\t\t\t\t\tp *= 1 / (len(g[v]) - 1)\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tcontinue\n",
    "\t\t\t\t#概率赋给子节点\n",
    "\t\t\t\tfor node in g[v]:\n",
    "\t\t\t\t\tif node not in visited:\n",
    "\t\t\t\t\t\tif node == target and not len(g[node]) - 1 or node == target and t == step:\n",
    "\t\t\t\t\t\t\treturn p\n",
    "\t\t\t\t\t\ttemp.append((node, p))\n",
    "\t\t\t\t\t\tvisited.append(node)\n",
    "\t\t\tif step == t:\n",
    "\t\t\t\treturn 0\n",
    "\t\t\tpending = temp\n",
    "\t\treturn 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef frogPosition(self, n, edges, t, target):\n",
    "\t\tif 1 == target and n == 1:\n",
    "\t\t\treturn 1\n",
    "\t\tg = [[] for _ in range(n + 1)]\n",
    "\t\tfor x, y in edges:\n",
    "\t\t\tg[x].append(y)\n",
    "\t\t\tg[y].append(x)\n",
    "\t\tpending = [(1, 1)]\n",
    "\t\tvisited = [1]\n",
    "\t\tstep = 0\n",
    "\t\twhile pending:\n",
    "\t\t\ttemp = []\n",
    "\t\t\tstep += 1\n",
    "\t\t\tfor v, p in pending:\n",
    "\t\t\t\tif v == 1:\n",
    "\t\t\t\t\tp = 1 / len(g[1])\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tif len(g[v]) - 1:\n",
    "\t\t\t\t\t\tp *= 1 / (len(g[v]) - 1)\n",
    "\t\t\t\tfor node in g[v]:\n",
    "\t\t\t\t\tif node not in visited:\n",
    "\t\t\t\t\t\tif node == target and not len(g[node]) - 1 or node == target and t == step:\n",
    "\t\t\t\t\t\t\treturn p\n",
    "\t\t\t\t\t\ttemp.append((node, p))\n",
    "\t\t\t\t\t\tvisited.append(node)\n",
    "\t\t\tif step == t:\n",
    "\t\t\t\treturn 0\n",
    "\t\t\tpending = temp\n",
    "\t\treturn 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for e in edges:\n",
    "            x, y = e[0], e[1]\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        # 跳向哪一个 ， 当时间用完 \n",
    "        g[1].append(-1)\n",
    "        def dfs(i, fa, left):\n",
    "            if left==0:\n",
    "                if i == target:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            if len(g[i])==1 and i==target:\n",
    "                return 1\n",
    "            for x in g[i]:\n",
    "                if x != fa:\n",
    "                    son = dfs(x, i, left-1)\n",
    "                    if son:\n",
    "                        return son * 1 / (len(g[i]) - 1)\n",
    "            return 0\n",
    "        return dfs(1, -1, t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        adj = defaultdict(list)\n",
    "        for a, b in edges :\n",
    "            adj[a].append(b)\n",
    "            adj[b].append(a)\n",
    "        adj[1].append(0)\n",
    "        # visited = [False for _ in range(n + 1)]\n",
    "        # visited[0] = True\n",
    "        # st = [(1, 1.0, t)]\n",
    "        # dq = deque([(1, 1, t)])\n",
    "        # while dq :\n",
    "        #     root, p, time = dq.popleft()\n",
    "        #     visited[root] = True\n",
    "        #     # m = sum(1 for child in adj[root] if not visited[child])\n",
    "        #     m = len(adj[root]) - 1\n",
    "        #     if root == target :\n",
    "        #         if m == 0 or time == 0:\n",
    "        #             # return p\n",
    "        #             return 1 / p\n",
    "        #         return 0.0\n",
    "        #     if time and m :\n",
    "        #         # p /= m\n",
    "        #         p *= m\n",
    "        #         for child in adj[root] :\n",
    "        #             if not visited[child] :\n",
    "        #                 dq.append((child, p, time - 1))\n",
    "        # return 0.0\n",
    "\n",
    "        q = [(1, 0, 1)]\n",
    "        while q and t >= 0 :\n",
    "            tmp = []\n",
    "            for root, parent, times in q :\n",
    "                m = len(adj[root]) - 1\n",
    "                if root == target :\n",
    "                    if not t or not m :\n",
    "                        return 1 / times\n",
    "                    return 0.0\n",
    "                times *= m\n",
    "                for child in adj[root] :\n",
    "                    if child != parent :\n",
    "                        tmp.append((child, root, times))\n",
    "            q = tmp\n",
    "            t -= 1\n",
    "        return 0.0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        adj = defaultdict(list)\n",
    "        for a, b in edges :\n",
    "            adj[a].append(b)\n",
    "            adj[b].append(a)\n",
    "        visited = [False for _ in range(n + 1)]\n",
    "        # st = [(1, 1.0, t)]\n",
    "        dq = deque([(1, 1, t)])\n",
    "        while dq :\n",
    "            root, p, time = dq.popleft()\n",
    "            visited[root] = True\n",
    "            m = sum(1 for child in adj[root] if not visited[child])\n",
    "            if root == target :\n",
    "                if m == 0 or time == 0:\n",
    "                    # return p\n",
    "                    return 1 / p\n",
    "                return 0.0\n",
    "            if time and m :\n",
    "                # p /= m\n",
    "                p *= m\n",
    "                for child in adj[root] :\n",
    "                    if not visited[child] :\n",
    "                        dq.append((child, p, time - 1))\n",
    "        return 0.0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "\n",
    "        for i, j in edges:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "        seen = [0] * (n + 1)\n",
    "        seen[1] = 1\n",
    "        q = [(1, 1.0)]\n",
    "\n",
    "        while q and t >= 0:\n",
    "            for _ in range(len(q)):\n",
    "                u, p = q.pop(0)\n",
    "                cnt = len(g[u]) - int(u != 1)\n",
    "                if u == target:\n",
    "                    return p if cnt * t == 0 else 0\n",
    "                for v in g[u]:\n",
    "                    if not seen[v]:\n",
    "                        seen[v] = 1\n",
    "                        q.append((v, p/cnt))\n",
    "            t -= 1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        net = [[] for _ in range(n+1)]\n",
    "        net[1].append(0)\n",
    "        for line in edges:\n",
    "            net[line[0]].append(line[1])\n",
    "            net[line[1]].append(line[0])\n",
    "\n",
    "        queue = [[1,0,1,t]] #(当前节点，父节点，概率,t_remain)\n",
    "        while queue and queue[0][3]>=0:\n",
    "            now, father, p, t_remain = queue[0][0], queue[0][1], queue[0][2], queue[0][3]\n",
    "            del(queue[0])\n",
    "            if now==target and (t_remain==0 or len(net[now])==1):\n",
    "                return p\n",
    "            for son in net[now]:\n",
    "                if son != father:\n",
    "                    queue.append([son,now,p*1/(len(net[now])-1),t_remain-1])\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for edge in edges:\n",
    "            k,v = edge[0], edge[1]\n",
    "            g[k].append(v)\n",
    "            g[v].append(k)\n",
    "        if n == 1:\n",
    "            return 1 \n",
    "        q = [(1, -1, 0, 1)] # 当前节点， 父亲节点， t， 到达当前节点的概率\n",
    "        while q: \n",
    "            cur, fa, cnt, p = q.pop(0)\n",
    "            if cur == target: # 当前节点为叶子节点\n",
    "                if t > cnt:\n",
    "                    if len(g[cur]) == 1 and fa != -1: return p # 考虑t > cnt\n",
    "                else:\n",
    "                    return p if t == cnt else 0     \n",
    "            for v in g[cur]:\n",
    "                if v == fa: continue\n",
    "                l = len(g[cur]) - 1 if fa != -1 else len(g[cur])\n",
    "                q.append((v, cur, cnt + 1, p / l)) \n",
    "        return 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef frogPosition(self, n, edges, t, target):\n",
    "\t\tif 1 == target and n == 1:\n",
    "\t\t\treturn 1\n",
    "\t\tg = [[] for _ in range(n + 1)]\n",
    "\t\tfor x, y in edges:\n",
    "\t\t\tg[x].append(y)\n",
    "\t\t\tg[y].append(x)\n",
    "\t\tpending = [(1, 1)]\n",
    "\t\tvisited = [1]\n",
    "\t\tstep = 0\n",
    "\t\twhile pending:\n",
    "\t\t\ttemp = []\n",
    "\t\t\tstep += 1\n",
    "\t\t\tfor v, p in pending:\n",
    "\t\t\t\t#第一层去往下一层的概率\n",
    "\t\t\t\tif v == 1:\n",
    "\t\t\t\t\tp = 1 / len(g[1])\n",
    "\t\t\t\t#其余层去往下一层的概率\n",
    "\t\t\t\telif len(g[v]) - 1:\n",
    "\t\t\t\t\t#有子节点\n",
    "\t\t\t\t\tp *= 1 / (len(g[v]) - 1)\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tcontinue\n",
    "\t\t\t\t#概率赋给子节点\n",
    "\t\t\t\tfor node in g[v]:\n",
    "\t\t\t\t\tif node not in visited:\n",
    "\t\t\t\t\t\tif node == target and not len(g[node]) - 1 or node == target and t == step:\n",
    "\t\t\t\t\t\t\treturn p\n",
    "\t\t\t\t\t\ttemp.append((node, p))\n",
    "\t\t\t\t\t\tvisited.append(node)\n",
    "\t\t\tif step == t:\n",
    "\t\t\t\treturn 0\n",
    "\t\t\tpending = temp\n",
    "\t\treturn 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        g = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        q = deque([(1, 1.0)])\n",
    "        vis = [False] * (n + 1)\n",
    "        vis[1] = True\n",
    "        while q and t >= 0:\n",
    "            for _ in range(len(q)):\n",
    "                u, p = q.popleft()\n",
    "                cnt = 0\n",
    "                for v in g[u]:\n",
    "                    if not vis[v]:\n",
    "                        cnt = cnt + 1\n",
    "                 \n",
    "                if u == target:\n",
    "                    return p if cnt * t == 0 else 0\n",
    "                for v in g[u]:\n",
    "                    if not vis[v]:\n",
    "                        vis[v] = True\n",
    "                        q.append((v, p / cnt))\n",
    "            t -= 1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for e in edges:\n",
    "            x, y = e[0], e[1]\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        # 跳向哪一个 ， 当时间用完 \n",
    "        g[1].append(-1)\n",
    "        def dfs(i, fa, left):\n",
    "            if left==0:\n",
    "                if i == target:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            if len(g[i])==1 and i==target:\n",
    "                return 1\n",
    "            for x in g[i]:\n",
    "                if x != fa:\n",
    "                    son = dfs(x, i, left-1)\n",
    "                    if son:\n",
    "                        return son * 1 / (len(g[i]) - 1)\n",
    "            return 0\n",
    "        return dfs(1, -1, t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        A = {}\n",
    "        for x, y in edges:\n",
    "            if x not in A:\n",
    "                A[x] = [y]\n",
    "            else:\n",
    "                A[x].append(y)\n",
    "            if y not in A:\n",
    "                A[y] = [x]\n",
    "            else:\n",
    "                A[y].append(x)\n",
    "        self.A = A\n",
    "        self.p = [0] * (n + 1)\n",
    "        pathSet = set([1])\n",
    "        path = [1]\n",
    "        self.t = t + 1\n",
    "        self.dfs(path, pathSet, 1)\n",
    "        return self.p[target]\n",
    "\n",
    "    def dfs(self, path, pathSet, p):\n",
    "        #print(path, pathSet)\n",
    "        if len(path) == 0:\n",
    "            return\n",
    "        current = path[-1]\n",
    "        if len(path) == self.t:\n",
    "            self.p[current] += p\n",
    "        else:\n",
    "            cand = []\n",
    "            for y in self.A[current]:\n",
    "                if y not in pathSet:\n",
    "                    cand.append(y)\n",
    "            if len(cand) == 0:\n",
    "                self.p[current] += p\n",
    "            else:\n",
    "                for y in cand:\n",
    "                    path.append(y)\n",
    "                    pathSet.add(y)\n",
    "                    self.dfs(path, pathSet, p / len(cand))\n",
    "                    #path.pop()\n",
    "                    #pathSet.discard(y)\n",
    "\n",
    "        current = path.pop()\n",
    "        pathSet.discard(current)\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef frogPosition(self, n, edges, t, target):\n",
    "\t\tif 1 == target and n == 1:\n",
    "\t\t\treturn 1\n",
    "\t\tg = [[] for _ in range(n + 1)]\n",
    "\t\tfor x, y in edges:\n",
    "\t\t\tg[x].append(y)\n",
    "\t\t\tg[y].append(x)\n",
    "\t\tpending = [(1, 1)]\n",
    "\t\tvisited = [1]\n",
    "\t\tstep = 0\n",
    "\t\twhile pending:\n",
    "\t\t\ttemp = []\n",
    "\t\t\tstep += 1\n",
    "\t\t\tfor v, p in pending:\n",
    "\t\t\t\t#第一层去往下一层的概率\n",
    "\t\t\t\tif v == 1:\n",
    "\t\t\t\t\tp = 1 / len(g[1])\n",
    "\t\t\t\t#其余层去往下一层的概率\n",
    "\t\t\t\telif len(g[v]) - 1:\n",
    "\t\t\t\t\t#有子节点\n",
    "\t\t\t\t\tp *= 1 / (len(g[v]) - 1)\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tcontinue\n",
    "\t\t\t\t#概率赋给子节点\n",
    "\t\t\t\tfor node in g[v]:\n",
    "\t\t\t\t\tif node not in visited:\n",
    "\t\t\t\t\t\t#找了了，走到头或者步数正好\n",
    "\t\t\t\t\t\tif node == target and not len(g[node]) - 1 or node == target and t == step:\n",
    "\t\t\t\t\t\t\treturn p\n",
    "\t\t\t\t\t\ttemp.append((node, p))\n",
    "\t\t\t\t\t\tvisited.append(node)\n",
    "\t\t\tif step == t:\n",
    "\t\t\t\treturn 0\n",
    "\t\t\tpending = temp\n",
    "\t\treturn 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        adj = defaultdict(list)\n",
    "        for a, b in edges :\n",
    "            adj[a].append(b)\n",
    "            adj[b].append(a)\n",
    "        visited = [False for _ in range(n + 1)]\n",
    "        # st = [(1, 1.0, t)]\n",
    "        dq = deque([(1, 1, t)])\n",
    "        while dq :\n",
    "            root, p, time = dq.popleft()\n",
    "            visited[root] = True\n",
    "            m = sum(1 for child in adj[root] if not visited[child])\n",
    "            if root == target :\n",
    "                if m == 0 or time == 0:\n",
    "                    # return p\n",
    "                    return 1 / p\n",
    "                return 0.0\n",
    "            if time and m :\n",
    "                # p /= m\n",
    "                p *= m\n",
    "                for child in adj[root] :\n",
    "                    if not visited[child] :\n",
    "                        dq.append((child, p, time - 1))\n",
    "        return 0.0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        adj = defaultdict(list)\n",
    "        for a, b in edges :\n",
    "            adj[a].append(b)\n",
    "            adj[b].append(a)\n",
    "        visited = [False for _ in range(n + 1)]\n",
    "        # st = [(1, 1.0, t)]\n",
    "        dq = deque([(1, 1, t)])\n",
    "        while dq :\n",
    "            root, p, time = dq.popleft()\n",
    "            visited[root] = True\n",
    "            m = sum(1 for child in adj[root] if not visited[child])\n",
    "            if root == target :\n",
    "                if m == 0 or time == 0:\n",
    "                    # return p\n",
    "                    return 1 / p\n",
    "                return 0.0\n",
    "            if time and m :\n",
    "                # p /= m\n",
    "                p *= m\n",
    "                for child in adj[root] :\n",
    "                    if not visited[child] :\n",
    "                        dq.append((child, p, time - 1))\n",
    "        return 0.0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef frogPosition(self, n, edges, t, target):\n",
    "\t\tif 1 == target and n == 1:\n",
    "\t\t\t\treturn 1\n",
    "\t\tg = [[] for _ in range(n + 1)]\n",
    "\t\tfor x, y in edges:\n",
    "\t\t\tg[x].append(y)\n",
    "\t\t\tg[y].append(x)\n",
    "\t\tpending = [(1, 1)]\n",
    "\t\tvisited = [1]\n",
    "\t\tstep = 0\n",
    "\t\twhile pending:\n",
    "\t\t\ttemp = []\n",
    "\t\t\tstep += 1\n",
    "\t\t\tfor v, p in pending:\n",
    "\t\t\t\tif v == 1:\n",
    "\t\t\t\t\tp = 1 / len(g[1])\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tif  len(g[v]) -1:\n",
    "\t\t\t\t\t\tp *= 1 / (len(g[v]) - 1)\n",
    "\t\t\t\tfor node in g[v]:\n",
    "\t\t\t\t\tif node not in visited:\n",
    "\t\t\t\t\t\tif node == target and not len(g[node])-1  or node == target and t == step:\n",
    "\t\t\t\t\t\t\treturn p\n",
    "\t\t\t\t\t\ttemp.append((node, p))\n",
    "\t\t\t\t\t\tvisited.append(node)\n",
    "\t\t\tif step == t:\n",
    "\t\t\t\treturn 0\n",
    "\t\t\tpending = temp\n",
    "\t\treturn 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef frogPosition(self, n, edges, t, target):\n",
    "\t\tif 1 == target and n == 1:\n",
    "\t\t\treturn 1\n",
    "\t\tg = [[] for _ in range(n + 1)]\n",
    "\t\tfor x, y in edges:\n",
    "\t\t\tg[x].append(y)\n",
    "\t\t\tg[y].append(x)\n",
    "\t\tpending = [(1, 1)]\n",
    "\t\tvisited = [1]\n",
    "\t\tstep = 0\n",
    "\t\twhile pending:\n",
    "\t\t\ttemp = []\n",
    "\t\t\tstep += 1\n",
    "\t\t\tfor v, p in pending:\n",
    "\t\t\t\t#第一层去往下一层的概率\n",
    "\t\t\t\tif v == 1:\n",
    "\t\t\t\t\tp = 1 / len(g[1])\n",
    "\t\t\t\t#其余层去往下一层的概率\n",
    "\t\t\t\telif len(g[v]) - 1:\n",
    "\t\t\t\t\t#有子节点\n",
    "\t\t\t\t\tp *= 1 / (len(g[v]) - 1)\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tcontinue\n",
    "\t\t\t\t#概率赋给子节点\n",
    "\t\t\t\tfor node in g[v]:\n",
    "\t\t\t\t\tif node not in visited:\n",
    "\t\t\t\t\t\tif node == target and not len(g[node]) - 1 or node == target and t == step:\n",
    "\t\t\t\t\t\t\treturn p\n",
    "\t\t\t\t\t\ttemp.append((node, p))\n",
    "\t\t\t\t\t\tvisited.append(node)\n",
    "\t\t\tif step == t:\n",
    "\t\t\t\treturn 0\n",
    "\t\t\tpending = temp\n",
    "\t\treturn 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        if target == 1:\n",
    "            if n == 1:return 1\n",
    "            else:return 0\n",
    "        m = [[] for i in range(n+1)]\n",
    "        for i,j in edges:\n",
    "            m[i].append(j)\n",
    "            m[j].append(i)\n",
    "\n",
    "        def dfs(i,s,last,m,target):\n",
    "            if target in m[i]:\n",
    "                a.append(s+[i])\n",
    "                return\n",
    "            for j in m[i]:\n",
    "                if j != last:\n",
    "                    dfs(j,s+[i],i,m,target)\n",
    "        a = []\n",
    "        dfs(1,[],-1,m,target)\n",
    "        a = a[0]\n",
    "        k = len(a)\n",
    "        \n",
    "        if t < k:return 0\n",
    "        if t > k and len(m[target]) > 1:return 0\n",
    "        res = 1\n",
    "        for i in a:\n",
    "            res *= (len(m[i]) - (1 if i != 1 else 0))\n",
    "        return 1/res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 1\n",
    "        self.flag = False\n",
    "        self.temp = []\n",
    "    def func1(self, track, children, t, target, childrens):\n",
    "        if t == 0:\n",
    "            if track[-1] == target:\n",
    "                self.temp.append(track[:])\n",
    "                self.flag = True\n",
    "            return\n",
    "        if track[-1] == target  and len(childrens[track[-1]]) ==1 and target!=1 :\n",
    "            self.temp.append(track[:])\n",
    "            self.flag = True\n",
    "            return\n",
    "        if not children:\n",
    "            return\n",
    "\n",
    "        for y in children:\n",
    "            if y not in track:\n",
    "                track.append(y)\n",
    "                self.func1(track, childrens[y], t - 1, target, childrens)\n",
    "                track.pop()\n",
    "\n",
    "    def frogPosition(self, n: int, edges, t: int, target: int) -> float:\n",
    "        if 1 == target and n==1:\n",
    "            return 1\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        track = [1]\n",
    "\n",
    "        self.func1(track,g[1], t, target, g)\n",
    "\n",
    "\n",
    "\n",
    "        if self.temp:\n",
    "            lst = self.temp[0]\n",
    "            for i in range(len(lst)-1):\n",
    "                a = len(g[lst[i]])\n",
    "                if i >0 and lst[i-1] in g[lst[i]]:\n",
    "                    a -= 1\n",
    "                self.res *=(1/a)\n",
    "\n",
    "        return self.res  if self.flag else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        # 1. build adjacency list of undirected graph\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "        \n",
    "        # 2. BFS\n",
    "        start = 0\n",
    "        queue = deque([(start, 1.0)])\n",
    "        visited = [False] * n \n",
    "        visited[start] = True \n",
    "        while queue and t >= 0:\n",
    "            for _ in range(len(queue)):\n",
    "                u, p = queue.popleft()\n",
    "                count = len(g[u]) - (u != start)  # number of unvisited vertices, the starting vertex don't have parent, other vertices have one parent count = len(g[u]) - 1\n",
    "                if u == target-1:\n",
    "                    if count == 0 or t == 0:\n",
    "                        return p \n",
    "                    else:\n",
    "                        return 0\n",
    "                \n",
    "                for v in g[u]:\n",
    "                    if not visited[v]:\n",
    "                        queue.append((v, p/count))\n",
    "                        visited[v] = True \n",
    "            t -= 1\n",
    "        \n",
    "        return 0\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        g[1] = [0]  # 减少额外判断的小技巧\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "\n",
    "        def dfs(x: int, fa: int, left_t: int) -> int:\n",
    "            # t 秒后必须在 target（恰好到达，或者 target 是叶子停在原地）\n",
    "            if left_t == 0: return x == target\n",
    "            if x == target: return len(g[x]) == 1\n",
    "            for y in g[x]:  # 遍历 x 的儿子 y\n",
    "                if y != fa:  # y 不能是父节点\n",
    "                    prod = dfs(y, x, left_t - 1)  # 寻找 target\n",
    "                    if prod: return prod * (len(g[x]) - 1)  # 乘上儿子个数，并直接返回\n",
    "            return 0  # 未找到 target\n",
    "\n",
    "        prod = dfs(1, 0, t)\n",
    "        return 1 / prod if prod else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        # n个节点无限图：给定邻接表： edges， 从顶点1开始，跳向相邻不重复节点，概率相同，t次后，位于节点target的概率\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        g[1] = [0] \n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        ans = 0\n",
    "        def dfs(x:int, fa:int, left_t:int, prod:int) -> True:\n",
    "            if x == target and (left_t == 0 or len(g[x]) == 1):\n",
    "                nonlocal ans \n",
    "                ans = 1 / prod\n",
    "                return True \n",
    "            if x == target or left_t == 0: return False \n",
    "            for y in g[x]:\n",
    "                if y != fa and dfs(y, x, left_t - 1, prod * (len(g[x]) - 1)):\n",
    "                    return True \n",
    "            return False\n",
    "        dfs(1, 0, t, 1)\n",
    "        return ans \n",
    "        # 1. 自顶向下(递)\n",
    "        # g = [[] for _ in range(n + 1)]\n",
    "        # g[1] = [0] # 减少额外的判断\n",
    "        # for x, y in edges:\n",
    "        #     g[x].append(y)\n",
    "        #     g[y].append(x)  # 建树\n",
    "        # ans = 0\n",
    "\n",
    "        # def dfs(x:int, fa:int, left_t:int, prod:int) -> True:\n",
    "        #     if x == target and (left_t == 0 or len(g[x]) == 1):\n",
    "        #         nonlocal ans\n",
    "        #         ans = 1 / prod\n",
    "        #         return True\n",
    "        #     if x == target or left_t == 0: return False\n",
    "        #     for y in g[x]: # 遍历x的儿子y\n",
    "        #         if y != fa and dfs(y, x, left_t - 1, prod * (len(g[x]) - 1)):\n",
    "        #             return True # 找到target就不再递归了\n",
    "        #     return False\n",
    "        \n",
    "        # dfs(1, 0, t, 1)\n",
    "        # return ans\n",
    "\n",
    "\n",
    "        # 2. 自底向上(归)\n",
    "        # g = [[] for _ in range(n + 1)]\n",
    "        # g[1] = [0] # 减少额外判断\n",
    "        # for x, y in edges:\n",
    "        #     g[x].append(y)\n",
    "        #     g[y].append(x) #建树\n",
    "        \n",
    "        # def dfs(x:int,  fa:int, left_t:int) -> int:\n",
    "        #     if left_t == 0: return x == target\n",
    "        #     if x == target: return len(g[x]) == 1\n",
    "        #     for y in g[x]: # 遍历x的儿子y\n",
    "        #         if y != fa: # y不能是父节点\n",
    "        #             prod = dfs(y, x, left_t - 1) #寻找target\n",
    "        #             if prod: return prod * (len(g[x]) - 1) # 乘上儿子个数\n",
    "        #     return 0 # 未找到0\n",
    "        # prod = dfs(1, 0, t)\n",
    "        # return 1 / prod if prod else 0\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        # node = collections.defaultdict(list)\n",
    "        node = [[] for i in range(n + 1)]\n",
    "        vis = [0] * (1 + n)\n",
    "\n",
    "        for a, b in edges:\n",
    "            node[a].append(b)\n",
    "            node[b].append(a)\n",
    "        \n",
    "        def dfs(i, t):\n",
    "            cnt = len(node[i])\n",
    "            if i > 1:\n",
    "                cnt -= 1\n",
    "            if cnt == 0 or t == 0:\n",
    "                return 1.0 if i == target else 0.0\n",
    "            # if t == 0:\n",
    "            #     return 0.0\n",
    "            vis[i] = 1\n",
    "            for ch in node[i]:\n",
    "                if vis[ch] == 0:\n",
    "                    p = dfs(ch, t-1)\n",
    "                    if p > 0:\n",
    "                        return p /(cnt)\n",
    "            return 0.0\n",
    "        return dfs(1, t)\n",
    "        # G = [[] for i in range(n + 1)]\n",
    "        # for i, j in edges:\n",
    "        #     G[i].append(j)\n",
    "        #     G[j].append(i)\n",
    "        # seen = [0] * (n + 1)\n",
    "\n",
    "        # def dfs(i, t):\n",
    "        #     nxt = len(G[i])\n",
    "        #     if i > 1:\n",
    "        #         nxt -= 1\n",
    "        #     if nxt == 0 or t == 0:\n",
    "        #         return 1.0 if i == target else 0.0\n",
    "        #     seen[i] = 1\n",
    "        #     for j in G[i]:\n",
    "        #         if not seen[j]:\n",
    "        #             p = dfs(j, t - 1)\n",
    "        #             if p > 0:\n",
    "        #                 return p / nxt\n",
    "        #     return 0.0\n",
    "\n",
    "        # return dfs(1, t)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        g[1] = [0]  # 减少额外判断的小技巧\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "        ans = 0\n",
    "        def dfs(x: int, fa: int, left_t: int, prod: int) -> True:\n",
    "            # t 秒后必须在 target（恰好到达，或者 target 是叶子停在原地）\n",
    "            if x == target and (left_t == 0 or len(g[x]) == 1):\n",
    "                nonlocal ans\n",
    "                ans = 1 / prod\n",
    "                return True\n",
    "            if x == target or left_t == 0: return False\n",
    "            for y in g[x]:  # 遍历 x 的儿子 y\n",
    "                if y != fa and dfs(y, x, left_t - 1, prod * (len(g[x]) - 1)):\n",
    "                    return True  # 找到 target 就不再递归了\n",
    "            return False  # 未找到 target\n",
    "        dfs(1, 0, t, 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        # node = collections.defaultdict(list)\n",
    "        node = [[] for i in range(n + 1)]\n",
    "        vis = [0] * (1 + n)\n",
    "\n",
    "        for a, b in edges:\n",
    "            node[a].append(b)\n",
    "            node[b].append(a)\n",
    "        \n",
    "        def dfs(i, t):\n",
    "            cnt = len(node[i])\n",
    "            if i > 1:\n",
    "                cnt -= 1\n",
    "            if cnt == 0 or t == 0:\n",
    "                return 1.0 if i == target else 0.0\n",
    "            # if t == 0:\n",
    "            #     return 0.0\n",
    "            vis[i] = 1\n",
    "            for ch in node[i]:\n",
    "                if vis[ch] == 0:\n",
    "                    p = dfs(ch, t-1)\n",
    "                    if p > 0:\n",
    "                        return p /(cnt)\n",
    "            return 0.0\n",
    "        return dfs(1, t)\n",
    "        # G = [[] for i in range(n + 1)]\n",
    "        # for i, j in edges:\n",
    "        #     G[i].append(j)\n",
    "        #     G[j].append(i)\n",
    "        # seen = [0] * (n + 1)\n",
    "\n",
    "        # def dfs(i, t):\n",
    "        #     nxt = len(G[i])\n",
    "        #     if i > 1:\n",
    "        #         nxt -= 1\n",
    "        #     if nxt == 0 or t == 0:\n",
    "        #         return 1.0 if i == target else 0.0\n",
    "        #     seen[i] = 1\n",
    "        #     for j in G[i]:\n",
    "        #         if not seen[j]:\n",
    "        #             p = dfs(j, t - 1)\n",
    "        #             if p > 0:\n",
    "        #                 return p / nxt\n",
    "        #     return 0.0\n",
    "\n",
    "        # return dfs(1, t)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        g = [[] for _ in range(n)]\n",
    "        g[0].append(-1)\n",
    "        for x, y in edges:\n",
    "            x -= 1\n",
    "            y -= 1\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        target -= 1\n",
    "        ans = 0\n",
    "        def dfs(x, fa, cnt, mul):\n",
    "            if x == target and (cnt == 0 or len(g[x]) == 1):\n",
    "                nonlocal ans\n",
    "                ans = 1 / mul\n",
    "                return True\n",
    "            \n",
    "            if x == target or cnt == 0: return False\n",
    "            for y in g[x]:\n",
    "                if y != fa and dfs(y, x, cnt - 1, mul * (len(g[x]) - 1)):\n",
    "                    return True\n",
    "            return False\n",
    "        dfs(0, -1, t, 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 1\n",
    "        self.flag = False\n",
    "        self.temp = []\n",
    "    def func1(self, track, children, t, target, childrens):\n",
    "        if t == 0:\n",
    "            if track[-1] == target:\n",
    "                self.temp.append(track[:])\n",
    "                self.flag = True\n",
    "            return\n",
    "        if track[-1] == target  and len(childrens[track[-1]]) ==1 and target!=1 :\n",
    "            self.temp.append(track[:])\n",
    "            self.flag = True\n",
    "            return\n",
    "        if not children:\n",
    "            return\n",
    "\n",
    "        for y in children:\n",
    "            if y not in track:\n",
    "                track.append(y)\n",
    "                self.func1(track, childrens[y], t - 1, target, childrens)\n",
    "                track.pop()\n",
    "\n",
    "    def frogPosition(self, n: int, edges, t: int, target: int) -> float:\n",
    "        if 1 == target and n==1:\n",
    "            return 1\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        track = [1]\n",
    "\n",
    "        self.func1(track,g[1], t, target, g)\n",
    "\n",
    "        if self.temp:\n",
    "            lst = self.temp[0]\n",
    "            for i in range(len(lst)-1):\n",
    "                a = len(g[lst[i]])\n",
    "                if i >0 and lst[i-1] in g[lst[i]]:\n",
    "                    a -= 1\n",
    "                self.res *=(1/a)\n",
    "\n",
    "        return self.res  if self.flag else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        if not edges:\n",
    "            return 1    \n",
    "\n",
    "        edge = [[] for _ in range(n + 1)]\n",
    "        for x, y in edges:\n",
    "            edge[x].append(y)\n",
    "            edge[y].append(x)\n",
    "\n",
    "        pending = [1]\n",
    "        score = [1]\n",
    "        pre = []\n",
    "\n",
    "        for k in range(t):\n",
    "            new_p = []  # pending\n",
    "            new_s = []  # score\n",
    "            for i in range(len(pending)):\n",
    "                x = pending[i]\n",
    "                tmp = [v for v in edge[x] if v not in pre]\n",
    "                n = len(tmp)\n",
    "                if n == 0:\n",
    "                    continue\n",
    "\n",
    "                if target in tmp:\n",
    "                    if k == t - 1 or len(edge[target]) == 1:\n",
    "                        return score[i] / n\n",
    "                    return 0\n",
    "\n",
    "                new_s += [score[i] / n] * n\n",
    "                new_p += tmp\n",
    "\n",
    "            pre = pending    \n",
    "            pending = new_p\n",
    "            score = new_s\n",
    "\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        g = [[] for _ in range(n+1)]\n",
    "        g[1] = [0]\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x) # 建树对了一半\n",
    "        ans = 0\n",
    "        def dfs(x : int,fa : int,left_T : int,prod: int) -> bool:\n",
    "            # t秒的时候刚好在target\n",
    "            # t秒的时候在target一直跳\n",
    "            # 因此有可能在结束之前经过target但是必须跳走\n",
    "            if x == target and (left_T == 0 or len(g[x]) == 1):\n",
    "                nonlocal ans \n",
    "                ans = 1/prod\n",
    "                return True\n",
    "            if x == target or left_T == 0: return False #\n",
    "            for y in g[x]:\n",
    "                if y != fa and dfs(y,x,left_T-1,prod*(len(g[x])-1)):\n",
    "                    return True\n",
    "            return False\n",
    "        dfs(1,0,t,1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef frogPosition(self, n, edges, t, target):\n",
    "\t\tif 1 == target and n == 1:\n",
    "\t\t\treturn 1\n",
    "\t\tg = [[] for _ in range(n + 1)]\n",
    "\t\tfor x, y in edges:\n",
    "\t\t\tg[x].append(y)\n",
    "\t\t\tg[y].append(x)\n",
    "\t\tpending = [(1, 1)]\n",
    "\t\tvisited = [1]\n",
    "\t\tstep = 0\n",
    "\t\twhile pending:\n",
    "\t\t\ttemp = []\n",
    "\t\t\tstep += 1\n",
    "\t\t\tfor v, p in pending:\n",
    "\t\t\t\tif v == 1:\n",
    "\t\t\t\t\tp = 1 / len(g[1])\n",
    "\t\t\t\telif len(g[v]) - 1:\n",
    "\t\t\t\t\t\tp *= 1 / (len(g[v]) - 1)\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tcontinue\n",
    "\t\t\t\tfor node in g[v]:\n",
    "\t\t\t\t\tif node not in visited:\n",
    "\t\t\t\t\t\tif node == target and not len(g[node]) - 1 or node == target and t == step:\n",
    "\t\t\t\t\t\t\treturn p\n",
    "\t\t\t\t\t\ttemp.append((node, p))\n",
    "\t\t\t\t\t\tvisited.append(node)\n",
    "\t\t\tif step == t:\n",
    "\t\t\t\treturn 0\n",
    "\t\t\tpending = temp\n",
    "\t\treturn 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        node_edges = [[] for _ in range(n)]\n",
    "        for s, e in edges:\n",
    "            node_edges[s-1].append(e)\n",
    "            node_edges[e-1].append(s)\n",
    "\n",
    "        candidates = [(1, 0, 1.0, True)]\n",
    "        path_nodes = [False] * (n + 1)\n",
    "\n",
    "        sum_prob = 0.0\n",
    "        while len(candidates) > 0:\n",
    "            idx, step, prob, first = candidates.pop(-1)\n",
    "            if not first:\n",
    "                path_nodes[idx] = False\n",
    "                continue\n",
    "\n",
    "            path_nodes[idx] = True\n",
    "            candidates.append((idx, step, prob, False))\n",
    "\n",
    "            if step == t:\n",
    "                if idx == target:\n",
    "                    sum_prob += prob\n",
    "                continue\n",
    "\n",
    "            current_valid = []\n",
    "            for next_idx in node_edges[idx - 1]:\n",
    "                if not path_nodes[next_idx]:\n",
    "                    current_valid.append(next_idx)\n",
    "\n",
    "            if len(current_valid) == 0:\n",
    "                if idx == target:\n",
    "                    sum_prob += prob\n",
    "                continue\n",
    "\n",
    "            new_prob = prob / len(current_valid)\n",
    "            for nidx in current_valid:\n",
    "                candidates.append((nidx, step + 1, new_prob, first))\n",
    "\n",
    "        return sum_prob\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        e = [[] for _ in range(n)]\n",
    "        for p, q in edges:\n",
    "            e[p - 1].append(q - 1)\n",
    "            e[q - 1].append(p - 1)\n",
    "        q = deque([[0, 1, t]])\n",
    "        vis = set()\n",
    "        time = t\n",
    "        while time >= 0 and q:\n",
    "            node, pro, time = q.popleft()\n",
    "            vis.add(node)\n",
    "            nxt = []\n",
    "            for nei in e[node]:\n",
    "                if nei not in vis:\n",
    "                    nxt.append(nei)\n",
    "            for nx in nxt:\n",
    "                q.append([nx, pro / len(nxt), time - 1])\n",
    "            if node == target - 1 and (len(nxt) == 0 and time >= 0 or time == 0):\n",
    "                return pro\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        d = collections.defaultdict(list)\n",
    "        res, l, visited = collections.Counter([1]), [1], {1}\n",
    "        for u, v in edges: \n",
    "            d[u].append(v)\n",
    "            d[v].append(u)\n",
    "        for _ in range(t):\n",
    "            new_l = []\n",
    "            for u in l:\n",
    "                tmp = [i for i in d[u] if i not in visited]\n",
    "                if tmp:                                    \n",
    "                    for v in tmp:\n",
    "                        visited.add(v)\n",
    "                        res[v] = res[u]/len(tmp)\n",
    "                    res[u] = 0\n",
    "                    new_l += tmp    \n",
    "            l = new_l\n",
    "        return res[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef frogPosition(self, n, edges, t, target):\n",
    "\t\tif 1 == target and n == 1:\n",
    "\t\t\treturn 1\n",
    "\t\tg = [[] for _ in range(n + 1)]\n",
    "\t\tfor x, y in edges:\n",
    "\t\t\tg[x].append(y)\n",
    "\t\t\tg[y].append(x)\n",
    "\t\tpending = [(1, 1)]\n",
    "\t\tvisited = [1]\n",
    "\t\tstep = 0\n",
    "\t\twhile pending:\n",
    "\t\t\ttemp = []\n",
    "\t\t\tstep += 1\n",
    "\t\t\tfor v, p in pending:\n",
    "\t\t\t\t#第一层去往下一层的概率\n",
    "\t\t\t\tif v == 1:\n",
    "\t\t\t\t\tp = 1 / len(g[1])\n",
    "\t\t\t\t#其余层去往下一层的概率\n",
    "\t\t\t\telif len(g[v]) - 1:\n",
    "\t\t\t\t\t#有子节点\n",
    "\t\t\t\t\tp *= 1 / (len(g[v]) - 1)\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tcontinue\n",
    "\t\t\t\t#概率赋给子节点\n",
    "\t\t\t\tfor node in g[v]:\n",
    "\t\t\t\t\tif node not in visited:\n",
    "\t\t\t\t\t\t#找了了，走到头或者步数正好\n",
    "\t\t\t\t\t\tif node == target and not len(g[node]) - 1 or node == target and t == step:\n",
    "\t\t\t\t\t\t\treturn p\n",
    "\t\t\t\t\t\ttemp.append((node, p))\n",
    "\t\t\t\t\t\tvisited.append(node)\n",
    "\t\t\tif step == t:\n",
    "\t\t\t\treturn 0\n",
    "\t\t\tpending = temp\n",
    "\t\treturn 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        if len(edges)==0 and target==1:\n",
    "            return 1\n",
    "        g=[[] for _ in range(n+1)]\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        visited=[False]*(n+1)\n",
    "        queue=[]\n",
    "        queue.append((1,1.0))\n",
    "        visited[1]=True\n",
    "        probability=[0]*(n+1)\n",
    "        time=0\n",
    "        while queue and time<t:\n",
    "            sz=len(queue)\n",
    "            for _ in range(sz): \n",
    "                head,p=queue.pop(0)\n",
    "                \n",
    "                cnt=0\n",
    "                nxts=[]\n",
    "                for nxt in g[head]:\n",
    "                    if not visited[nxt]:\n",
    "                        cnt+=1\n",
    "                        nxts.append(nxt)\n",
    "                for nxt in nxts:\n",
    "                    probability[head]=0\n",
    "                    visited[nxt]=True\n",
    "                    probability[nxt]=p*(1/cnt)\n",
    "                    queue.append((nxt,p*(1/cnt)))\n",
    "            time+=1\n",
    "        return probability[target]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        g[1].append(0)\n",
    "        ans = 0\n",
    "        def dfs(x, fa, time, prod):\n",
    "            if x == target and (time == 0 or len(g[x]) == 1):\n",
    "                nonlocal ans\n",
    "                ans = 1 / prod\n",
    "                return True\n",
    "            if x == target or time == 0: return False\n",
    "            for y in g[x]:\n",
    "                if y == fa: continue\n",
    "                if dfs(y, x, time - 1, prod * (len(g[x]) - 1)): return True\n",
    "            return False\n",
    "        dfs(1, 0, t, 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        if n==1:\n",
    "            return 1.0\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        g[1].append(0)\n",
    "        vis = set()  # 记录青蛙跳过的节点\n",
    "        q = deque()\n",
    "        q.append((1, 1))\n",
    "        while q and t>=0:\n",
    "            size = len(q)\n",
    "            while size:\n",
    "                x, p = q.popleft()\n",
    "                if target == x and (t == 0 or all([child in vis for child in g[x]])):\n",
    "                    return p\n",
    "                p /= (len(g[x]) - 1 if len(g[x]) > 1 else 1)\n",
    "                vis.add(x)\n",
    "                size -= 1\n",
    "                for y in g[x]:\n",
    "                    if y not in vis:\n",
    "                        q.append((y, p))\n",
    "\n",
    "            t -= 1\n",
    "\n",
    "        return 0.0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        g = defaultdict(list) \n",
    "        for a, b in edges:\n",
    "            g[a].append(b) \n",
    "            g[b].append(a) \n",
    "\n",
    "        vis= [0] * (n+1)\n",
    "        D = [0] * (n+1)\n",
    "        Q = deque([(0, 1)])\n",
    "        vis[1] = 1 \n",
    "        tree = defaultdict(list)\n",
    "        while Q:\n",
    "            d, u = Q.popleft() \n",
    "            for v in g[u]:\n",
    "                if not vis[v]:\n",
    "                    vis[v] = 1\n",
    "                    tree[u].append(v) \n",
    "                    D[v] = d+1 \n",
    "                    Q.append((d+1, v))\n",
    "        \n",
    "        Q.append((1, 1))\n",
    "        #print(g) \n",
    "        #print(tree) \n",
    "        while Q:\n",
    "            p, u = Q.popleft() \n",
    "            if u == target:\n",
    "                if t == D[u]:\n",
    "                    return p\n",
    "                if t < D[u]:\n",
    "                    return 0 \n",
    "                if t > D[u]:\n",
    "                    if len(tree[u]) == 0:\n",
    "                        return p \n",
    "                    else:\n",
    "                        return 0  \n",
    "            sz = len(tree[u])\n",
    "            for v in tree[u]:\n",
    "                Q.append((p*(1./sz), v))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        g[1] = [0]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        ans = 0\n",
    "        def dfs(x, fa, left_t, prod):\n",
    "            if x == target and (left_t == 0 or len(g[x]) == 1):\n",
    "                nonlocal ans\n",
    "                ans = 1 / prod\n",
    "                return True\n",
    "            \n",
    "            if x == target or left_t == 0: return False\n",
    "            for y in g[x]:\n",
    "                if y != fa and dfs(y, x, left_t - 1, prod * (len(g[x]) - 1)):\n",
    "                    return True\n",
    "            return False\n",
    "        dfs(1, 0, t, 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        g[1] = [0]  # 减少额外判断的小技巧\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(x: int, fa: int, left_t: int, prod: int) -> True:\n",
    "            # t 秒后必须在 target（恰好到达，或者 target 是叶子停在原地）\n",
    "            if x == target and (left_t == 0 or len(g[x]) == 1):\n",
    "                nonlocal ans\n",
    "                ans = 1 / prod\n",
    "                return True\n",
    "            if x == target or left_t == 0: return False\n",
    "            for y in g[x]:  # 遍历 x 的儿子 y\n",
    "                if y != fa and dfs(y, x, left_t - 1, prod * (len(g[x]) - 1)):\n",
    "                    return True  # 找到 target 就不再递归了\n",
    "            return False  # 未找到 target\n",
    "\n",
    "        dfs(1, 0, t, 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        node = collections.defaultdict(list)\n",
    "        vis = [0] * (1 + n)\n",
    "\n",
    "        for a, b in edges:\n",
    "            node[a].append(b)\n",
    "            node[b].append(a)\n",
    "        \n",
    "        def dfs(i, t):\n",
    "            cnt = len(node[i])\n",
    "            if i > 1:\n",
    "                cnt -= 1\n",
    "            if cnt == 0 or t == 0:\n",
    "                return 1.0 if i == target else 0.0\n",
    "            # if t == 0:\n",
    "            #     return 0.0\n",
    "            vis[i] = 1\n",
    "            for ch in node[i]:\n",
    "                if vis[ch] == 0:\n",
    "                    p = dfs(ch, t-1)\n",
    "                    if p > 0:\n",
    "                        return p /(cnt)\n",
    "            return 0.0\n",
    "        return dfs(1, t)\n",
    "        # G = [[] for i in range(n + 1)]\n",
    "        # for i, j in edges:\n",
    "        #     G[i].append(j)\n",
    "        #     G[j].append(i)\n",
    "        # seen = [0] * (n + 1)\n",
    "\n",
    "        # def dfs(i, t):\n",
    "        #     nxt = len(G[i])\n",
    "        #     if i > 1:\n",
    "        #         nxt -= 1\n",
    "        #     if nxt == 0 or t == 0:\n",
    "        #         return 1.0 if i == target else 0.0\n",
    "        #     seen[i] = 1\n",
    "        #     for j in G[i]:\n",
    "        #         if not seen[j]:\n",
    "        #             p = dfs(j, t - 1)\n",
    "        #             if p > 0:\n",
    "        #                 return p / nxt\n",
    "        #     return 0.0\n",
    "\n",
    "        # return dfs(1, t)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        g = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        q = deque([(1, 1.0)])\n",
    "        vis = [False] * (n + 1)\n",
    "        vis[1] = True\n",
    "        while q and t >= 0:\n",
    "            for _ in range(len(q)):\n",
    "                u, p = q.popleft()\n",
    "                cnt = len(g[u]) - int(u != 1)\n",
    "                if u == target:\n",
    "                    return p if cnt * t == 0 else 0\n",
    "                for v in g[u]:\n",
    "                    if not vis[v]:\n",
    "                        vis[v] = True\n",
    "                        q.append((v, p / cnt))\n",
    "            t -= 1\n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        g[1] = [0]\n",
    "\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        def dfs(x, fa, rest):\n",
    "            if rest == 0:\n",
    "                return x == target\n",
    "            if x == target:\n",
    "                return len(g[x]) == 1\n",
    "                \n",
    "            # 其他情况进行遍历\n",
    "            for y in g[x]:\n",
    "                if y != fa and dfs(y, x, rest-1):\n",
    "                    return (len(g[x]) - 1) * dfs(y, x, rest-1)\n",
    "            return 0\n",
    "\n",
    "        ans = dfs(1, 0, t)\n",
    "        if ans == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1 / ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        ans = 0\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        g[1] = [0]  # 为根节点增加一个父亲\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        def dfs(x, fa, left_t):\n",
    "            if left_t == 0: return x == target\n",
    "            if x == target: return len(g[x]) == 1\n",
    "            for y in g[x]:\n",
    "                if y == fa: continue\n",
    "                pro = dfs(y, x, left_t - 1)\n",
    "                if pro:\n",
    "                    return pro * (len(g[x]) - 1)\n",
    "            return 0\n",
    "        pro = dfs(1, 0, t)\n",
    "        return 1 / pro if pro > 0 else 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        relation = [[] for _ in range(n + 1)]\n",
    "        for a, b in edges:\n",
    "            relation[a].append(b)\n",
    "            relation[b].append(a)\n",
    "        \n",
    "        self.res=0\n",
    "\n",
    "        def dfs(step,lastnode,curr,add):\n",
    "\n",
    "            if step>t:\n",
    "                return False\n",
    "            if curr==target:\n",
    "                if step==t or len(relation[curr])==1 :\n",
    "                    if curr==1:\n",
    "                        return False\n",
    "                    self.res=1/float(add)\n",
    "                    return True\n",
    "                \n",
    "            for v in relation[curr]:\n",
    "                temp=1\n",
    "                if curr==1:\n",
    "                    temp=0\n",
    "                if v!=lastnode and dfs(step+1,curr,v,add*(len(relation[curr])-temp)):\n",
    "                    return True\n",
    "            return False\n",
    "        dfs(0,0,1,1)\n",
    "        if not edges:\n",
    "            return 1\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class Flag:\n",
    "        def __init__(self):\n",
    "            self.flag1 = 0\n",
    "            self.flag2 = 0\n",
    "\n",
    "        def add(self, idx):\n",
    "            nflag = Solution.Flag()\n",
    "\n",
    "            if idx < 60:\n",
    "                nflag.flag1 = self.flag1 | (1 << (idx - 1))\n",
    "                nflag.flag2 = self.flag2\n",
    "            else:\n",
    "                nflag.flag1 = self.flag1\n",
    "                nflag.flag2 = self.flag2 | (1 << (idx - 60))\n",
    "            return nflag\n",
    "\n",
    "        def check(self, idx):\n",
    "            if idx < 60:\n",
    "                return (self.flag1 & (1 << (idx - 1))) == 0\n",
    "            else:\n",
    "                return (self.flag2 & (1 << (idx - 60))) == 0\n",
    "\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        node_edges = [[] for _ in range(n)]\n",
    "        for s, e in edges:\n",
    "            node_edges[s-1].append(e)\n",
    "            node_edges[e-1].append(s)\n",
    "\n",
    "        flag = Solution.Flag()\n",
    "        candidates = [(1, flag.add(1), 0, 1.0)]\n",
    "\n",
    "        sum_prob = 0.0\n",
    "        while len(candidates) > 0:\n",
    "            idx, flag, step, prob = candidates.pop(-1)\n",
    "\n",
    "            if step == t:\n",
    "                if idx == target:\n",
    "                    sum_prob += prob\n",
    "                continue\n",
    "\n",
    "            current_valid = []\n",
    "            for next_idx in node_edges[idx - 1]:\n",
    "                if flag.check(next_idx):\n",
    "                    current_valid.append(next_idx)\n",
    "\n",
    "            if len(current_valid) == 0:\n",
    "                if idx == target:\n",
    "                    sum_prob += prob\n",
    "                continue\n",
    "\n",
    "            new_prob = prob / len(current_valid)\n",
    "            for nidx in current_valid:\n",
    "                candidates.append((nidx, flag.add(nidx), step + 1, new_prob))\n",
    "\n",
    "        return sum_prob\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        # node = collections.defaultdict(list)\n",
    "        node = [[] for i in range(n + 1)]\n",
    "        vis = [0] * (1 + n)\n",
    "\n",
    "        for a, b in edges:\n",
    "            node[a].append(b)\n",
    "            node[b].append(a)\n",
    "        \n",
    "        def dfs(i, t):\n",
    "            cnt = len(node[i])\n",
    "            if i > 1:\n",
    "                cnt -= 1\n",
    "            if cnt == 0 or t == 0:\n",
    "                return 1.0 if i == target else 0.0\n",
    "            # if t == 0:\n",
    "            #     return 0.0\n",
    "            vis[i] = 1\n",
    "            for ch in node[i]:\n",
    "                if not vis[ch] :\n",
    "                    p = dfs(ch, t-1)\n",
    "                    if p > 0:\n",
    "                        return p /(cnt)\n",
    "            return 0.0\n",
    "        return dfs(1, t)\n",
    "        # G = [[] for i in range(n + 1)]\n",
    "        # for i, j in edges:\n",
    "        #     G[i].append(j)\n",
    "        #     G[j].append(i)\n",
    "        # seen = [0] * (n + 1)\n",
    "\n",
    "        # def dfs(i, t):\n",
    "        #     nxt = len(G[i])\n",
    "        #     if i > 1:\n",
    "        #         nxt -= 1\n",
    "        #     if nxt == 0 or t == 0:\n",
    "        #         return 1.0 if i == target else 0.0\n",
    "        #     seen[i] = 1\n",
    "        #     for j in G[i]:\n",
    "        #         if not seen[j]:\n",
    "        #             p = dfs(j, t - 1)\n",
    "        #             if p > 0:\n",
    "        #                 return p / nxt\n",
    "        #     return 0.0\n",
    "\n",
    "        # return dfs(1, t)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        g[1] = [0]  \n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  \n",
    "        ans = 0\n",
    "\n",
    "        def dfs(x: int, fa: int, left_t: int, prod: int) -> True:\n",
    "            if x == target and (left_t == 0 or len(g[x]) == 1):\n",
    "                nonlocal ans\n",
    "                ans = 1 / prod\n",
    "                return True\n",
    "            if x == target or left_t == 0: return False\n",
    "            for y in g[x]:  \n",
    "                if y != fa and dfs(y, x, left_t - 1, prod * (len(g[x]) - 1)):\n",
    "                    return True  \n",
    "            return False \n",
    "        dfs(1, 0, t, 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        tree = [[] for _ in range(n+1)]\n",
    "        tree[1] = [0]\n",
    "        for edge in edges:\n",
    "            tree[edge[0]].append(edge[1])\n",
    "            tree[edge[1]].append(edge[0])\n",
    "\n",
    "        ans = 0\n",
    "        def dfs(x, fa, left_t, prod):\n",
    "            if x == target and (left_t == 0 or len(tree[x]) == 1):\n",
    "                nonlocal ans\n",
    "                ans = 1 / prod\n",
    "                return True\n",
    "            if x == target or left_t == 0: return False\n",
    "            for y in tree[x]:\n",
    "                if y != fa and dfs(y, x, left_t - 1, prod * (len(tree[x]) - 1)):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        dfs(1, 0, t, 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        node_edges = [[] for _ in range(n)]\n",
    "        for s, e in edges:\n",
    "            node_edges[s-1].append(e)\n",
    "            node_edges[e-1].append(s)\n",
    "\n",
    "        candidates = [[1, 0, 1.0, True]]\n",
    "        path_nodes = [False] * (n + 1)\n",
    "\n",
    "        sum_prob = 0.0\n",
    "        while len(candidates) > 0:\n",
    "            first = candidates[-1][-1]\n",
    "            if first:\n",
    "                candidates[-1][-1] = False\n",
    "                idx, step, prob, _ = candidates[-1]\n",
    "                path_nodes[idx] = True\n",
    "            else:\n",
    "                idx, _, _, _ = candidates.pop(-1)\n",
    "                path_nodes[idx] = False\n",
    "                continue\n",
    "\n",
    "            if step == t:\n",
    "                if idx == target:\n",
    "                    sum_prob += prob\n",
    "                continue\n",
    "\n",
    "            current_valid = []\n",
    "            for next_idx in node_edges[idx - 1]:\n",
    "                if not path_nodes[next_idx]:\n",
    "                    current_valid.append(next_idx)\n",
    "\n",
    "            if len(current_valid) == 0:\n",
    "                if idx == target:\n",
    "                    sum_prob += prob\n",
    "                continue\n",
    "\n",
    "            new_prob = prob / len(current_valid)\n",
    "            for nidx in current_valid:\n",
    "                candidates.append([nidx, step + 1, new_prob, True])\n",
    "\n",
    "        return sum_prob\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)\n",
    "        g[0].append(-1)\n",
    "        def dfs(x: int, fa: int, t_left: int):\n",
    "            if t_left == 0: \n",
    "                return 1 if x == target - 1 else 0\n",
    "            if x == target - 1:\n",
    "                return 1 if len(g[x]) == 1 else 0\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dominator = dfs(y, x, t_left - 1)\n",
    "                    if dominator > 0:\n",
    "                        return dominator * (len(g[x]) - 1)\n",
    "            return 0\n",
    "        \n",
    "        dominator = dfs(0, -1, t)\n",
    "        return 1 / dominator if dominator > 0 else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        #1 <= n <= 100\n",
    "        # edges.length == n - 1\n",
    "        # edges[i].length == 2\n",
    "\n",
    "        # 可以把节点 1 添加一个 0 号邻居，从而避免判断当前节点为根节点 1，也避免了特判 n=1的情况。\n",
    "        g = [[] for _ in range(n+1)]\n",
    "        g[1] = [0]\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x) # 建树对了一半\n",
    "\n",
    "        def dfs(x : int,fa : int,left_T : int) -> bool:\n",
    "            # t秒的时候刚好在target\n",
    "            # t秒的时候在target一直跳\n",
    "            # 因此有可能在结束之前经过target但是必须跳走\n",
    "\n",
    "            # 感觉想清楚边界条件就对了一半了\n",
    "            if left_T == 0: return x ==target\n",
    "            if x == target: return len(g[x]) == 1\n",
    "            for y in g[x]: # 遍历 x 的儿子 y\n",
    "                if y !=fa: # y 不能是父节点\n",
    "                    prod = dfs(y,x,left_T-1)\n",
    "                    if prod:\n",
    "                        return prod*(len(g[x])-1)\n",
    "            return 0  # 未找到 target\n",
    "        prod = dfs(1,0,t)\n",
    "        return 1/prod if prod else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        graph = [[] for _ in range(len(edges)+2)]\n",
    "        for i, j in edges:\n",
    "            graph[i].append(j)\n",
    "            graph[j].append(i)\n",
    "\n",
    "        seen = [0] * (len(edges) + 2)\n",
    "\n",
    "        def dfs(node, time):\n",
    "            if time == 0:\n",
    "                if node != target:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return 1\n",
    "            else:\n",
    "                if node == target:\n",
    "                    if node == 1:\n",
    "                        if len(graph[node]) == 0:\n",
    "                            return 1\n",
    "                        else:\n",
    "                            return 0\n",
    "                    else:\n",
    "                        if len(graph[node]) == 1:\n",
    "                            return 1\n",
    "                    \n",
    "            seen[node] = 1\n",
    "            for j in graph[node]:\n",
    "                if seen[j] != 1:\n",
    "                    if node == 1:\n",
    "                        p = dfs(j, time - 1) / len(graph[node])\n",
    "                    else:\n",
    "                        p = dfs(j, time - 1) / (len(graph[node]) - 1)\n",
    "                    if p > 0:\n",
    "                        return p\n",
    "            \n",
    "            return 0\n",
    "        \n",
    "        p = dfs(1, t)\n",
    "        return p\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: [], t: int, target: int) -> float:\n",
    "        _row = [0 for i in range(0, n + 1)]\n",
    "        grid = [_row[:] for i in range(0, n + 1)]\n",
    "        for x,y in edges:\n",
    "            grid[x][y] = 1\n",
    "            grid[y][x] = 1\n",
    "        \n",
    "        result = []\n",
    "        stack = [[1, [1], 1.0]]\n",
    "        count = t\n",
    "        while stack and count > 0:\n",
    "            #print(stack)\n",
    "            _list = []\n",
    "\n",
    "            for x,path,val in stack:\n",
    "                nstep = []\n",
    "                for y in range(0, n + 1):\n",
    "                    if grid[x][y] == 1 and y not in path:\n",
    "                        nstep.append(y)\n",
    "                #msg = str(x) + '>' + str(nstep); print(msg)\n",
    "                \n",
    "                if len(nstep) > 0:\n",
    "                    nval = val / len(nstep)\n",
    "                    for y in nstep:\n",
    "                        np = path[:]\n",
    "                        np.append(y)\n",
    "                        _list.append([y, np, nval])\n",
    "                else:\n",
    "                    result.append([x,path,val])\n",
    "            \n",
    "            stack[:] = _list[:]\n",
    "            count -= 1\n",
    "        [result.append(tmp) for tmp in stack]\n",
    "        \n",
    "        chance = 0.0\n",
    "        for x,path,val in result:\n",
    "            if target == x:\n",
    "                chance = val\n",
    "                break\n",
    "\n",
    "        return chance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        # #自底向上\n",
    "        g=[[] for _ in range(n+1)]\n",
    "        g[1]=[0]#给节点1添一个父节点  减少额外的判断\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        # def dfs(x,fa,left_t):\n",
    "        #     #t 秒后必须在 target（恰好到达，或者 target 是叶子停在原地）left_t:剩余时间\n",
    "        #     if left_t==0:return x==target\n",
    "        #     #len(g[x])==1 表示x是叶子结点\n",
    "        #     if x==target:return len(g[x])==1\n",
    "        #     for y in g[x]:\n",
    "        #         if y==fa:continue\n",
    "        #         prod=dfs(y,x,left_t-1)\n",
    "        #         if prod:return prod*(len(g[x])-1)\n",
    "        #     return 0#没有找到\n",
    "        \n",
    "        # prod=dfs(1,0,t)\n",
    "        # return 1/prod if prod else 0\n",
    "\n",
    "        #自顶向下\n",
    "        ans=0\n",
    "        def dfs(x,fa,left_t,prod):\n",
    "            # t 秒后必须在 target（恰好到达，或者 target 是叶子停在原地）\n",
    "            if x==target and (left_t==0 or len(g[x])==1):\n",
    "                nonlocal ans\n",
    "                ans=1/prod\n",
    "                return True\n",
    "\n",
    "            if x==target or left_t==0:return False\n",
    "            for y in g[x]:\n",
    "                if y==fa:continue\n",
    "                if dfs(y,x,left_t-1,prod*(len(g[x])-1)):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        dfs(1,0,t,1)\n",
    "        return ans \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        ans = 0\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        g[1] = [0]  # 为根节点增加一个父亲\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        def dfs(x, fa, left_t, pro):\n",
    "            if x == target and (len(g[x]) == 1 or left_t == 0):\n",
    "                nonlocal ans\n",
    "                ans = 1 / pro\n",
    "                return True\n",
    "            if x == target or left_t == 0:\n",
    "                return False\n",
    "            for y in g[x]:\n",
    "                if y != fa and dfs(y, x, left_t - 1, pro * (len(g[x]) - 1)):\n",
    "                    return True\n",
    "            return False\n",
    "        dfs(1, 0, t, 1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        relation = [[] for _ in range(n + 1)]\n",
    "        for a, b in edges:\n",
    "            relation[a].append(b)\n",
    "            relation[b].append(a)\n",
    "        \n",
    "        self.res=0\n",
    "\n",
    "        def dfs(step,lastnode,curr,add):\n",
    "\n",
    "            if step>t:\n",
    "                return False\n",
    "            if curr==target:\n",
    "                if step==t or len(relation[curr])==1 :\n",
    "                    if curr==1:\n",
    "                        return False\n",
    "                    self.res=1/float(add)\n",
    "                    return True\n",
    "                \n",
    "            for v in relation[curr]:\n",
    "                temp=1\n",
    "                if curr==1:\n",
    "                    temp=0\n",
    "                if v!=lastnode and dfs(step+1,curr,v,add*(len(relation[curr])-temp)):\n",
    "                    return True\n",
    "            return False\n",
    "        dfs(0,0,1,1)\n",
    "        if not edges:\n",
    "            return 1\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        g[1].append(0)\n",
    "        ans = 0\n",
    "        def dfs(x, fa, time, prod):\n",
    "            if x == target and (time == 0 or len(g[x]) == 1):\n",
    "                nonlocal ans\n",
    "                ans = 1 / prod\n",
    "                return True\n",
    "            if x == target or time == 0: return False\n",
    "            for y in g[x]:\n",
    "                if y == fa: continue\n",
    "                if dfs(y, x, time - 1, prod * (len(g[x]) - 1)): return True\n",
    "            return False\n",
    "        dfs(1, 0, t, 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        grid = [[] for _ in range(n + 1)]\n",
    "\n",
    "        for a,b in edges:\n",
    "            grid[a].append(b)\n",
    "            grid[b].append(a)\n",
    "\n",
    "        ans = [0] * (n + 1)\n",
    "        ans[1] = 1.0\n",
    "\n",
    "        def dfs(cur : int,fa : int,k : int) -> None:\n",
    "            if k == 0:\n",
    "                return\n",
    "\n",
    "            if cur == target:\n",
    "                ans[0] = -1\n",
    "                \n",
    "                if k != 0:\n",
    "                    if cur != 1 and len(grid[cur]) - 1 != 0:\n",
    "                        ans[target] = 0\n",
    "                    \n",
    "                    if cur == 1 and len(grid[cur]) != 0:\n",
    "                        ans[target] = 0\n",
    "                return\n",
    "\n",
    "            for nxt in grid[cur]:\n",
    "                if nxt != fa:\n",
    "                    size = (len(grid[cur]) - 1) if cur != 1 else len(grid[cur])\n",
    "                    ans[nxt] = ans[cur] / size\n",
    "                    dfs(nxt,cur,k - 1)\n",
    "\n",
    "                    if ans[0] == -1:\n",
    "                        return\n",
    "\n",
    "        dfs(1,-1,t)\n",
    "\n",
    "        return ans[target]\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        node = collections.defaultdict(list)\n",
    "        vis = [0] * (1 + n)\n",
    "\n",
    "        for a, b in edges:\n",
    "            node[a].append(b)\n",
    "            node[b].append(a)\n",
    "        \n",
    "        def dfs(i, t):\n",
    "            cnt = len(node[i])\n",
    "            if i > 1:\n",
    "                cnt -= 1\n",
    "            if cnt == 0 or t == 0:\n",
    "                return 1.0 if i == target else 0.0\n",
    "            # if t == 0:\n",
    "            #     return 0.0\n",
    "            vis[i] = 1\n",
    "            for ch in node[i]:\n",
    "                if vis[ch] == 0:\n",
    "                    p = dfs(ch, t-1)\n",
    "                    if p > 0:\n",
    "                        return p /(cnt)\n",
    "            return 0.0\n",
    "        return dfs(1, t)\n",
    "        # G = [[] for i in range(n + 1)]\n",
    "        # for i, j in edges:\n",
    "        #     G[i].append(j)\n",
    "        #     G[j].append(i)\n",
    "        # seen = [0] * (n + 1)\n",
    "\n",
    "        # def dfs(i, t):\n",
    "        #     nxt = len(G[i])\n",
    "        #     if i > 1:\n",
    "        #         nxt -= 1\n",
    "        #     if nxt == 0 or t == 0:\n",
    "        #         return 1.0 if i == target else 0.0\n",
    "        #     seen[i] = 1\n",
    "        #     for j in G[i]:\n",
    "        #         if not seen[j]:\n",
    "        #             p = dfs(j, t - 1)\n",
    "        #             if p > 0:\n",
    "        #                 return p / nxt\n",
    "        #     return 0.0\n",
    "\n",
    "        # return dfs(1, t)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        node = collections.defaultdict(list)\n",
    "        vis = [0] * (1 + n)\n",
    "\n",
    "        for a, b in edges:\n",
    "            node[a].append(b)\n",
    "            node[b].append(a)\n",
    "        \n",
    "        def dfs(i, t):\n",
    "            cnt = len(node[i])\n",
    "            if i > 1:\n",
    "                cnt -= 1\n",
    "            if cnt == 0 or t == 0:\n",
    "                return 1.0 if i == target else 0.0\n",
    "            # if t == 0:\n",
    "            #     return 0.0\n",
    "            vis[i] = 1\n",
    "            for ch in node[i]:\n",
    "                if vis[ch] == 0:\n",
    "                    p = dfs(ch, t-1)\n",
    "                    if p > 0:\n",
    "                        return p /(cnt)\n",
    "            return 0.0\n",
    "        return dfs(1, t)\n",
    "        # G = [[] for i in range(n + 1)]\n",
    "        # for i, j in edges:\n",
    "        #     G[i].append(j)\n",
    "        #     G[j].append(i)\n",
    "        # seen = [0] * (n + 1)\n",
    "\n",
    "        # def dfs(i, t):\n",
    "        #     nxt = len(G[i])\n",
    "        #     if i > 1:\n",
    "        #         nxt -= 1\n",
    "        #     if nxt == 0 or t == 0:\n",
    "        #         return 1.0 if i == target else 0.0\n",
    "        #     seen[i] = 1\n",
    "        #     for j in G[i]:\n",
    "        #         if not seen[j]:\n",
    "        #             p = dfs(j, t - 1)\n",
    "        #             if p > 0:\n",
    "        #                 return p / nxt\n",
    "        #     return 0.0\n",
    "\n",
    "        # return dfs(1, t)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        g = [[] for _ in range(n+1)]\n",
    "        g[1] = [0]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        print(g)\n",
    "        def dfs(x, fa, left_t):\n",
    "            if left_t == 0: return x == target\n",
    "            if x == target: return len(g[x]) == 1\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    prob = dfs(y, x, left_t - 1)\n",
    "                    if prob:\n",
    "                        return prob * (len(g[x]) - 1)\n",
    "            return 0\n",
    "        \n",
    "        prob = dfs(1, 0, t)\n",
    "        return 1/prob if prob else 0\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        # #自底向上\n",
    "        g=[[] for _ in range(n+1)]\n",
    "        g[1]=[0]#给节点1添一个父节点  减少额外的判断\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        # def dfs(x,fa,left_t):\n",
    "        #     #t 秒后必须在 target（恰好到达，或者 target 是叶子停在原地）left_t:剩余时间\n",
    "        #     if left_t==0:return x==target\n",
    "        #     #len(g[x])==1 表示x是叶子结点\n",
    "        #     if x==target:return len(g[x])==1\n",
    "        #     for y in g[x]:\n",
    "        #         if y==fa:continue\n",
    "        #         prod=dfs(y,x,left_t-1)\n",
    "        #         if prod:return prod*(len(g[x])-1)\n",
    "        #     return 0#没有找到\n",
    "        \n",
    "        # prod=dfs(1,0,t)\n",
    "        # return 1/prod if prod else 0\n",
    "\n",
    "        #自顶向下\n",
    "        ans=0\n",
    "        def dfs(x,fa,left_t,prod):\n",
    "            # t 秒后必须在 target（恰好到达，或者 target 是叶子停在原地）\n",
    "            if x==target and (left_t==0 or len(g[x])==1):\n",
    "                nonlocal ans\n",
    "                ans=1/prod\n",
    "                return True\n",
    "\n",
    "            if x==target or left_t==0:return False\n",
    "            for y in g[x]:\n",
    "                if y==fa:continue\n",
    "                if dfs(y,x,left_t-1,prod*(len(g[x])-1)):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        dfs(1,0,t,1)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: [], t: int, target: int) -> float:\n",
    "        _row = [0 for i in range(0, n + 1)]\n",
    "        grid = [_row[:] for i in range(0, n + 1)]\n",
    "        for x,y in edges:\n",
    "            grid[x][y] = 1\n",
    "            grid[y][x] = 1\n",
    "        \n",
    "        result = []\n",
    "        stack = [[1, [1], 1.0]]\n",
    "        count = t\n",
    "        while stack and count > 0:\n",
    "            #print(stack)\n",
    "            _list = []\n",
    "\n",
    "            for x,path,val in stack:\n",
    "                nstep = []\n",
    "                for y in range(0, n + 1):\n",
    "                    if grid[x][y] == 1 and y not in path:\n",
    "                        nstep.append(y)\n",
    "                #msg = str(x) + '>' + str(nstep); print(msg)\n",
    "                \n",
    "                if len(nstep) > 0:\n",
    "                    nval = val / len(nstep)\n",
    "                    for y in nstep:\n",
    "                        np = path[:]\n",
    "                        np.append(y)\n",
    "                        _list.append([y, np, nval])\n",
    "                else:\n",
    "                    result.append([x,path,val])\n",
    "            \n",
    "            stack[:] = _list[:]\n",
    "            count -= 1\n",
    "        [result.append(tmp) for tmp in stack]\n",
    "        \n",
    "        chance = 0.0\n",
    "        for x,path,val in result:\n",
    "            if target == x:\n",
    "                chance = val\n",
    "                break\n",
    "\n",
    "        return chance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        temp = collections.defaultdict(list)\n",
    "        n = 1\n",
    "        if target == 1 and not edges:\n",
    "            return 1\n",
    "        for num1, num2 in edges:\n",
    "            temp[num1].append(num2)\n",
    "            temp[num2].append(num1)\n",
    "            n = max(n, num1, num2)\n",
    "        visited = set()\n",
    "        record = collections.defaultdict(list)\n",
    "        queue = [1]\n",
    "        visited.add(1)\n",
    "        dp = [[0 for _ in range(t+1)] for _ in range(n+1)]\n",
    "        dp[1][0] = 1\n",
    "        count = 1\n",
    "        cur = set()\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                visited.add(node)\n",
    "                for nxt in temp[node]:\n",
    "                    if nxt not in visited:\n",
    "                        record[node].append(nxt)\n",
    "                        queue.append(nxt)\n",
    "                m = len(record[node])\n",
    "                if m == 0:\n",
    "                    cur.add(node)\n",
    "                for nxt in record[node]:\n",
    "                    dp[nxt][count] += dp[node][count-1]*1/m\n",
    "            # print(cur, count)\n",
    "            if count == t:\n",
    "                if target not in cur:\n",
    "                    return dp[target][t]\n",
    "                j = t\n",
    "                while dp[target][j] == 0:\n",
    "                    j -= 1\n",
    "                return dp[target][j]\n",
    "            count += 1\n",
    "        j = t\n",
    "        # print(cur)\n",
    "        if target not in cur:\n",
    "            return 0\n",
    "        while dp[target][j] == 0:\n",
    "            j -= 1\n",
    "        return dp[target][j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        edgeDict = {}\n",
    "        for l in edges:\n",
    "            if l[0] not in edgeDict:\n",
    "                edgeDict[l[0]] = []\n",
    "            if l[1] not in edgeDict:\n",
    "                edgeDict[l[1]] = []\n",
    "            edgeDict[l[0]].append(l[1])\n",
    "            edgeDict[l[1]].append(l[0])\n",
    "        # print(edgeDict)\n",
    "        edgeDict[1].append(0)\n",
    "        print(edgeDict)\n",
    "        result = 0\n",
    "        def dfs(fa,count,now,target,t):\n",
    "            nonlocal result\n",
    "            if t == 0:\n",
    "                if now == target:\n",
    "                    # nonlocal result\n",
    "                    print(count)\n",
    "                    result = 1/count\n",
    "                    print(result)\n",
    "                return\n",
    "            nextList = edgeDict[now]\n",
    "            if len(nextList) - 1 == 0:\n",
    "                if now == target:\n",
    "                    # nonlocal result\n",
    "                    print(count)\n",
    "                    result = 1/count\n",
    "                    return\n",
    "            if now == target or t == 0:\n",
    "                return\n",
    "            for nextNode in nextList:\n",
    "                if nextNode != fa:\n",
    "                    dfs(now,count*(len(nextList)-1),nextNode,target,t-1)\n",
    "        dfs(0,1,1,target,t)\n",
    "        # print(result)\n",
    "        return result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        graph = [[] for _ in range(n + 1)]\n",
    "        for x, y in edges:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        info = set([])\n",
    "\n",
    "        answer = 0\n",
    "\n",
    "        def dfs(node, v, count):\n",
    "            nonlocal answer\n",
    "            info.add(node)\n",
    "            cur_nodes = [cur for cur in graph[node] if cur not in info]\n",
    "            s = len(cur_nodes)\n",
    "\n",
    "            if node == target and (s == 0 or count == 0):\n",
    "                answer = v\n",
    "                return v\n",
    "            if count == 0:\n",
    "                return 0\n",
    "\n",
    "            for c in cur_nodes:\n",
    "                dfs(c, v * (1 / s), count - 1)\n",
    "\n",
    "        dfs(1, 1, t)\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        g = defaultdict(list)\n",
    "        g[1] = [0]\n",
    "        for i, j in edges:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "        \n",
    "        visited = [False] * (n + 1)\n",
    "\n",
    "        def dfs(i, t):\n",
    "            visited[i] = True\n",
    "            nxt = len(g[i])   # 当前节点的相邻节点个数\n",
    "            if nxt == 1 or t == 0:   # 如果没有相邻节点或时间耗尽\n",
    "                return 1 if i == target else 0\n",
    "            for j in g[i]:      # 遍历i的相邻节点\n",
    "                if not visited[j]:\n",
    "                    p = dfs(j, t - 1)\n",
    "                    if p > 0:\n",
    "                        return p / (nxt - 1)\n",
    "            return 0\n",
    "\n",
    "        return dfs(1, t)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:\n",
    "        # 1. 建图\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        g[1].append(0)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        # 2. DFS 递归\n",
    "        #      参数：（当前节点，当前节点父节点，当前概率，当前秒数）\n",
    "        ans = 0\n",
    "        def dfs(x: int, fa: int, p: float, cnt: int):\n",
    "            if cnt > t: return \n",
    "            if x == target:\n",
    "                nonlocal ans\n",
    "                ans = p if cnt == t or len(g[x]) == 1 else 0\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y, x, p * (1 / (len(g[x]) - 1)), cnt + 1)\n",
    "        # 递归入口\n",
    "        dfs(1, 0, 1, 0)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
